{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Deletions to Make Array Divisible"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #number-theory #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #数论 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组可以被整除的最少删除次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个正整数数组&nbsp;<code>nums</code> 和&nbsp;<code>numsDivide</code>&nbsp;。你可以从&nbsp;<code>nums</code>&nbsp;中删除任意数目的元素。</p>\n",
    "\n",
    "<p>请你返回使 <code>nums</code>&nbsp;中 <strong>最小</strong>&nbsp;元素可以整除 <code>numsDivide</code>&nbsp;中所有元素的 <strong>最少</strong>&nbsp;删除次数。如果无法得到这样的元素，返回 <code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>y % x == 0</code>&nbsp;，那么我们说整数&nbsp;<code>x</code>&nbsp;整除&nbsp;<code>y</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "[2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。\n",
    "我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。\n",
    "[3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。\n",
    "可以证明 2 是最少删除次数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>nums = [4,3,6], numsDivide = [8,2,6,10]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>\n",
    "我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。\n",
    "没有任何办法可以达到这一目的。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length, numsDivide.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i], numsDivide[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-deletions-to-make-array-divisible](https://leetcode.cn/problems/minimum-deletions-to-make-array-divisible/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-deletions-to-make-array-divisible](https://leetcode.cn/problems/minimum-deletions-to-make-array-divisible/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,2,4,3]\\n[9,6,9,3,15]', '[4,3,6]\\n[8,2,6,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        \n",
    "        cands = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        \n",
    "        n = len(cands)\n",
    "        \n",
    "        if n % 2: return -1\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, j):\n",
    "            if i > j:\n",
    "                return 0\n",
    "\n",
    "            # if cands[i+1] - cands[i] < cands[j] - cands[j-1]:               \n",
    "            #     return min(cands[i+1] - cands[i] + dp(i+2, j), x + dp(i+1, j-1))\n",
    "            # else:\n",
    "            return min(cands[j] - cands[j-1] + dp(i, j-2), cands[i+1] - cands[i] + dp(i+2, j), x + dp(i+1, j-1))\n",
    "        \n",
    "        \n",
    "        return dp(0, n-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1 == s2:\n",
    "            return 0\n",
    "        p = [i for i, (x, y) in enumerate(zip(s1, s2)) if x != y]\n",
    "        if len(p) % 2:\n",
    "            return -1\n",
    "        f0, f1 = 0, x\n",
    "        for i, j in pairwise(p):\n",
    "            f0, f1 = f1, min(f1 + x, f0 + (j - i) * 2)\n",
    "        return f1 // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        cnt1 = Counter(s1)\n",
    "        cnt2 = Counter(s2)\n",
    "        if (cnt2['1'] - cnt1['1']) % 2 != 0:\n",
    "            return -1\n",
    "        \n",
    "        tmp = []\n",
    "        for i, (c1, c2) in enumerate(zip(s1, s2)):\n",
    "            if c1 != c2:\n",
    "                tmp.append(i)\n",
    "        \n",
    "        # dp2: \n",
    "        # dp0: 表示该数字结尾，下一个跟他用距离结算\n",
    "        # dp1: 下一个跟前面的某一个用x结算, 还没结算完成\n",
    "        \n",
    "        # dp0 结束\n",
    "        # dp1 还没结束\n",
    "        \n",
    "        if not tmp:\n",
    "            return 0\n",
    "        \n",
    "        dp0 = min(tmp[1] - tmp[0], x)\n",
    "        dp1 = 0\n",
    "        for i in range(2, len(tmp), 2):\n",
    "            dp0, dp1 = min(dp1 + min(tmp[i] - tmp[i-1], x) + x, dp0 + min(tmp[i+1] - tmp[i], x)), min(dp0, dp1 + min(tmp[i] - tmp[i-1], x))\n",
    "        return dp0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.x = 0\n",
    "        self.diff = []\n",
    "        self.INT_MAX = 2 ** 31\n",
    "\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        self.x = x\n",
    "        n: int = len(s1)\n",
    "        # 记录需要操作的下标的位置\n",
    "        diff = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                diff.append(i)\n",
    "        self.diff = diff\n",
    "\n",
    "        m: int = len(diff)\n",
    "        if m == 0:\n",
    "            return 0\n",
    "        if m % 2 == 1:\n",
    "            return -1\n",
    "\n",
    "        return int(self.dfs(m - 1))\n",
    "\n",
    "    # 记忆化搜索\n",
    "    # n: 还剩余多少字符需要处理\n",
    "    @cache\n",
    "    def dfs(self, n: int) -> int:\n",
    "        if n == -2:\n",
    "            return self.INT_MAX\n",
    "        if n == -1:\n",
    "            return 0\n",
    "        # 进行第一种操作\n",
    "        a = self.dfs(n - 1) + self.x / 2\n",
    "        # 进行第二种操作\n",
    "        b = self.dfs(n - 2) + self.diff[n] - self.diff[n - 1]\n",
    "        return min(a, b)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "\n",
    "        t = list()\n",
    "        for i in range(len(s1)):\n",
    "            if s1[i] != s2[i]:\n",
    "                t.append(i)\n",
    "\n",
    "        # print(len(l))\n",
    "        # 奇数个要反转的一定不可能\n",
    "        if len(t) & 1 == 1:\n",
    "            return -1\n",
    "\n",
    "        # 本质上是两两合并代价最小\n",
    "\n",
    "        n = len(t)\n",
    "\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for l in range(2, n+1, 2):\n",
    "            for i in range(n-l+1):\n",
    "                j = i + l - 1\n",
    "                dp[i][j] = dp[i+1][j-1] + min(x, t[j]-t[i])\n",
    "                if i + 2 < n: \n",
    "                    dp[i][j] = min(dp[i][j], min(x, t[i+1]-t[i])+dp[i+2][j])\n",
    "                if j - 2 > -1:\n",
    "                    dp[i][j] = min(dp[i][j], min(x, t[j]-t[j-1])+dp[i][j-2])\n",
    "\n",
    "                # for k in range(i+1, j, 2):\n",
    "                #     dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j])\n",
    "\n",
    "        return dp[0][n-1] if n > 0 else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # ---------------------暴力方法会超时啊--------------------------------\n",
    "        # 剪枝\n",
    "        # l = list()\n",
    "        # for i in range(len(s1)):\n",
    "        #     if s1[i] != s2[i]:\n",
    "        #         l.append(i)\n",
    "\n",
    "        # # print(len(l))\n",
    "        # # 奇数个要反转的一定不可能\n",
    "        # if len(l) & 1 == 1:\n",
    "        #     return -1\n",
    "        # min_s = 1e9\n",
    "\n",
    "        # v = [0]*len(l)\n",
    "        # @cache\n",
    "        # def cost(n, c):\n",
    "        #     nonlocal min_s, v\n",
    "\n",
    "        #     if n == len(l):\n",
    "        #         min_s = min(min_s, c)\n",
    "        #         # print(c)\n",
    "        #     else:\n",
    "        #         for i in range(len(l)):\n",
    "        #             if v[i] == 0:\n",
    "        #                 v[i] = 1\n",
    "        #                 for j in range(i+1, len(l)):\n",
    "        #                     if v[j] == 0:\n",
    "        #                         v[j] = 1\n",
    "        #                         cost(n+2, c + min(x, l[j]-l[i]))\n",
    "        #                         v[j] = 0\n",
    "        #                 v[i] = 0\n",
    "\n",
    "        # cost(0, 0)\n",
    "\n",
    "        # return min_s\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        diffs = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                diffs.append(i)\n",
    "        \n",
    "        ndiff = len(diffs)\n",
    "        if ndiff == 0:\n",
    "            return 0\n",
    "        if ndiff % 2 != 0:\n",
    "            return -1\n",
    "        \n",
    "        dp = [[-1]*ndiff for _ in range(ndiff)]\n",
    "        for i in range(ndiff-1):\n",
    "            dp[i][i+1] = min(x, diffs[i+1] - diffs[i])\n",
    "        # print(diffs)\n",
    "        def calc_dp(i, j):\n",
    "            if dp[i][j] != -1:\n",
    "                return dp[i][j]\n",
    "            \n",
    "            a1 = calc_dp(i+1,j-1) + x\n",
    "            a2 = calc_dp(i+2,j) + diffs[i+1]-diffs[i]\n",
    "            a3 = calc_dp(i,j-2) + diffs[j]-diffs[j-1]\n",
    "            dp[i][j] = min(a1, a2, a3)\n",
    "            return dp[i][j]\n",
    "\n",
    "        sol = calc_dp(0, ndiff-1)\n",
    "        return sol\n",
    "\n",
    "# print(Solution().minOperations(\"100010010100111100001110101111100001001101011010100111101011100100011111110001011001001\", \"000001100010010011111101100101111011101110010001001010100101011100011110000111010011010\", 6))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                a.append(i)\n",
    "                \n",
    "        if len(a) % 2 == 1:\n",
    "            return -1\n",
    "\n",
    "        n = len(a)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "    \n",
    "        f = [[10000000] * (n + 1) for i in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            j = i + 1\n",
    "            if j >= n:\n",
    "                continue\n",
    "            f[i][j] = min(a[j] - a[i], x)\n",
    "        for d in range(3, n + 1):\n",
    "            for l in range(0, n):\n",
    "                if d == 1:\n",
    "                    f[l][l] = 10000000\n",
    "                r = l + d - 1\n",
    "                if r >= n:\n",
    "                    continue\n",
    "                f[l][r] = min([f[l + 2][r] + a[l + 1] - a[l], f[l][r - 2] + a[r] - a[r - 1], f[l + 1][r - 1] + min(a[r] - a[l], x)])\n",
    "\n",
    "        \n",
    "        return f[0][n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n=len(s1)\n",
    "        ls=[]\n",
    "        for i in range(n):\n",
    "            if s1[i]!=s2[i]:\n",
    "                ls.append(i)\n",
    "        if len(ls)%2==1:\n",
    "            return -1\n",
    "        to_change=ls\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def deal(pt=0, end=len(to_change)) :\n",
    "            if pt >= end :\n",
    "                return 0\n",
    "            to_ret = deal(pt+2, end) + (to_change[pt+1]-to_change[pt])\n",
    "            if to_change[pt+1]-to_change[pt] == 1 :\n",
    "                return to_ret\n",
    "            \n",
    "            for pnext in range(pt+1, end, 2) :\n",
    "                rett = deal(pt+1, pnext) + deal(pnext+1, end) + x\n",
    "                to_ret = min(to_ret, rett)\n",
    "            return to_ret\n",
    "        return deal()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        pos = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        n = len(pos)\n",
    "        if n % 2:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "\n",
    "            a = min(x, pos[r] - pos[l]) + dfs(l + 1, r - 1)\n",
    "            b = min(x, pos[l + 1] - pos[l]) + dfs(l + 2, r)\n",
    "            c = min(x, pos[r] - pos[r - 1]) + dfs(l, r - 2)\n",
    "            return min(a, b, c)\n",
    "\n",
    "        ans = dfs(0, n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        pos = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        n = len(pos)\n",
    "        if n % 2:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(l, r):\n",
    "            if l >= r:\n",
    "                return 0\n",
    "\n",
    "            a = min(x, pos[r] - pos[l]) + dfs(l + 1, r - 1)\n",
    "            b = min(x, pos[l + 1] - pos[l]) + dfs(l + 2, r)\n",
    "            c = min(x, pos[r] - pos[r - 1]) + dfs(l, r - 2)\n",
    "            return min(a, b, c)\n",
    "\n",
    "        ans = dfs(0, n - 1)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        li = [] \n",
    "        for i in range(n):\n",
    "            if s1[i]!=s2[i]:\n",
    "                li.append(i)\n",
    "        m = len(li)\n",
    "        if m%2:\n",
    "            return -1 \n",
    "        if m==0:\n",
    "            return 0\n",
    "        \n",
    "        @cache \n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i==j-1:\n",
    "                return min(li[j]-li[i], x)\n",
    "            ans = x+dfs(i+1, j-1)\n",
    "            k = 1\n",
    "            while i+k+1<j:\n",
    "                ans = min(ans, dfs(i, i+k) + dfs(i+k+1, j))\n",
    "                k += 2\n",
    "            return ans \n",
    "        \n",
    "        return dfs(0, m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        loc = []\n",
    "        for i in range(len(s1)):\n",
    "            if(s1[i] != s2[i]):\n",
    "                loc.append(i)\n",
    "        if(len(loc) % 2 == 1):\n",
    "            return -1\n",
    "\n",
    "        self.dic = {}\n",
    "        def cal(start, end):\n",
    "            if(start >= end):\n",
    "                return 0\n",
    "            if((start, end) in self.dic):\n",
    "                return self.dic[(start, end)]\n",
    "            if(start + 1 == end):\n",
    "                if(loc[end] - loc[start] < x):\n",
    "                    ans = loc[end] - loc[start]\n",
    "                else:\n",
    "                    ans = x\n",
    "            else:\n",
    "                res = []\n",
    "                j = start + 1\n",
    "                while(j <= end):\n",
    "                    if(loc[j] - loc[start] < x):\n",
    "                        ans = loc[j] - loc[start]\n",
    "                    else:\n",
    "                        ans = x\n",
    "                    temp = ans + cal(start + 1, j - 1) + cal(j+1, end)\n",
    "                    res.append(temp)\n",
    "                    j += 2\n",
    "                ans = min(res)\n",
    "            self.dic[(start, end)] = ans\n",
    "            return ans\n",
    "\n",
    "        return cal(0, len(loc)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        lt = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                lt.append(i)\n",
    "        m = len(lt)\n",
    "        if m % 2 == 1:\n",
    "            return -1\n",
    "        print(lt)\n",
    "        \n",
    "        @functools.cache\n",
    "        def dfs(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            return min(x + dfs(p + 1, q - 1), min(x, lt[p + 1] - lt[p]) + dfs(p + 2, q), min(x, lt[q] - lt[q - 1]) + dfs(p, q - 2))\n",
    "        \n",
    "        return dfs(0, m - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1 == s2: return 0\n",
    "        pos = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        n = len(pos)\n",
    "        if n % 2: return -1\n",
    "        @cache\n",
    "        def dfs(l, r):\n",
    "            if l >= r: return 0\n",
    "            a = pos[l + 1] - pos[l] + dfs(l + 2, r)\n",
    "            b = x + dfs(l + 1, r - 1)\n",
    "            c = pos[r] - pos[r - 1] + dfs(l, r - 2)\n",
    "            return min(a, b, c)\n",
    "\n",
    "        return dfs(0, n - 1)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        arr = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                arr.append(i)\n",
    "        if len(arr) % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        ## 统计差异点，差异点必须两两交换\n",
    "        ## 贪心思路 操作一 只适合相邻的差异点\n",
    "        ## 操作二 增加一个计数用于统计前面使用过的次数\n",
    "        @cache\n",
    "        def dfs(i, c):\n",
    "            if i < 0:\n",
    "                return inf if c else 0\n",
    "            res = dfs(i-1, c+1) + x\n",
    "            if i:\n",
    "                res = min(res, dfs(i-2, c) + arr[i] - arr[i-1])\n",
    "            if c:\n",
    "                res = min(res, dfs(i-1, c-1))\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(arr)-1, 0)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = [i for i in range(n) if s1[i] != s2[i]]\n",
    "        m = len(a)\n",
    "        if m % 2:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def g(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            if p == q:\n",
    "                return math.inf\n",
    "            if p == m-1:\n",
    "                return math.inf\n",
    "            ans = a[p+1] - a[p] + g(p+2, q)\n",
    "            if a[p+1] == a[p]+1:\n",
    "                return ans\n",
    "            for k in range(p+1, q+1):\n",
    "                ans = min(ans, x + g(p+1, k-1) + g(k+1, q))\n",
    "            return ans\n",
    "        \n",
    "        ans = g(0, m-1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        res = [i for i in range(len(s1)) if s1[i] != s2[i]]\n",
    "        if len(res) % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        cache = {}\n",
    "\n",
    "        def dp(left, right):\n",
    "            if f'{left}-{right}' in cache:\n",
    "                return cache[f'{left}-{right}']\n",
    "            if left > right:\n",
    "                return 0\n",
    "\n",
    "            a = dp(left + 1, right - 1) + min(x, res[right] - res[left])  # n***n\n",
    "            b = dp(left, right - 2) + min(x, res[right] - res[right - 1])  # n***nmm\n",
    "            c = dp(left + 2, right) + min(x, res[left + 1] - res[left])  # mmn***n\n",
    "            result = min(a, b, c)\n",
    "\n",
    "            cache[f'{left}-{right}'] = result\n",
    "            return result\n",
    "\n",
    "        return dp(0, len(res) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "sys.setrecursionlimit(9999999)\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "'''\n",
    "\"100010010100111100001110101111100001001101011010100111101011100100011111110001011001001\"\n",
    "\"000001100010010011111101100101111011101110010001001010100101011100011110000111010011010\"\n",
    "6\n",
    "\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        arr = []\n",
    "        n = len(s1)\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                arr.append(i)\n",
    "\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "\n",
    "        if len(arr) % 2:\n",
    "            return -1\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=128000000)\n",
    "        def dp(ii, jj):\n",
    "            if ii > jj:\n",
    "                return 0\n",
    "\n",
    "            val1 = (arr[ii+1]-arr[ii]) + dp(ii+2, jj)\n",
    "\n",
    "            val2 = 0x7f7f7f7f7f7f7f\n",
    "            for i in range(ii+1, jj+1, 2):\n",
    "                val2 = min(val2, x + dp(ii+1, i-1) + dp(i+1, jj))\n",
    "            return min(val1, val2)\n",
    "\n",
    "        return dp(0, len(arr)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if sum(1 for i in range(len(s1)) if s1[i] != s2[i]) % 2 != 0:\n",
    "            return -1\n",
    "        n = len(s1)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, times, reverse=False):\n",
    "            if i == n:\n",
    "                if times != 0 or reverse:\n",
    "                    return x * n\n",
    "                return 0\n",
    "            if (s1[i] == s2[i]) != reverse:\n",
    "                return dfs(i + 1, times)\n",
    "            i += 1\n",
    "            res = min(1 + dfs(i, times, True), x + dfs(i, times + 1))\n",
    "            if times > 0:\n",
    "                res = min(res, dfs(i, times - 1))\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "\n",
    "def min(a: int, b: int) -> int:\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(index: int, flip1Count: int, prevFlip2: bool) -> int:\n",
    "            if index == n:\n",
    "                return 0 if flip1Count == 0 else INF\n",
    "\n",
    "            cur = nums1[index] ^ prevFlip2\n",
    "            target = nums2[index]\n",
    "            if cur == target:\n",
    "                return dfs(index + 1, flip1Count, False)\n",
    "\n",
    "            # 反转1\n",
    "            res = dfs(index + 1, flip1Count + 1, False) + x\n",
    "            if flip1Count > 0:\n",
    "                res = min(res, dfs(index + 1, flip1Count - 1, False))\n",
    "            # 反转2\n",
    "            if index < n - 1:\n",
    "                res = min(res, dfs(index + 1, flip1Count, True) + 1)\n",
    "            return res\n",
    "\n",
    "        nums1 = [int(i) for i in s1]\n",
    "        nums2 = [int(i) for i in s2]\n",
    "        n = len(s1)\n",
    "        res = dfs(0, 0, False)\n",
    "        dfs.cache_clear()\n",
    "        return res if res < INF else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        n = len(s1)\n",
    "        memoset = {}\n",
    "        def dfs(i, j, f):\n",
    "            if i >= n:\n",
    "                return inf if j > 0 or f else 0\n",
    "            if (i,j,f) in memoset:\n",
    "                return memoset[(i, j, f)]\n",
    "            cur = inf\n",
    "            if (s1[i] == s2[i]) == (not f):\n",
    "                return dfs(i+1, j, False)\n",
    "            cur = min(cur, dfs(i+1, j+1, False) + x, dfs(i+1, j, True) + 1)\n",
    "            if j:\n",
    "                cur = min(cur, dfs(i+1, j-1, False))\n",
    "            memoset[(i, j, f)] = cur\n",
    "            return cur\n",
    "        return dfs(0, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        n=len(s1)\n",
    "        # @cache\n",
    "        # def dfs(i: int, j: int , b) -> int:\n",
    "        #     if i < 0:\n",
    "        #         return inf if j or b else 0\n",
    "        #     if s1[i]==s2[i]:\n",
    "        #         if b:\n",
    "        #             return dfs(i - 1, j, True)+1  #相同且前面有则+1，没有则跳过\n",
    "        #         return dfs(i - 1, j, b)\n",
    "        #     if s1[i]!=s2[i]:        \n",
    "        #         if b:\n",
    "        #             return dfs(i - 1, j, False)  #不同且前面有，这次不算，没有得操作\n",
    "        #         res = min(dfs(i - 1, j + 1, b) + x, dfs(i - 1, j , True) + 1)\n",
    "        #     if j:  # 可以免费反转\n",
    "        #         res = min(res, dfs(i - 1, j - 1,b))\n",
    "        #     return res\n",
    "        # return dfs(len(s1) - 1, 0, False)\n",
    "        f=[[[0]*2 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(-1,n):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                for b in range(2):\n",
    "                    if i < 0:\n",
    "                        f[i][j][b]= inf if j or b else 0\n",
    "                        continue\n",
    "                    if s1[i]==s2[i]:\n",
    "                        if b:\n",
    "                            f[i][j][b] = f[i - 1][j][True]+1  #相同且前面有则+1，没有则跳过\n",
    "                            continue\n",
    "                        f[i][j][b] =f[i - 1][j][False]\n",
    "                        continue\n",
    "                    if s1[i]!=s2[i]:        \n",
    "                        if b:\n",
    "                            f[i][j][b]= f[i - 1][j][False]  #不同且前面有，这次不算，没有得操作\n",
    "                            continue\n",
    "                        f[i][j][b]= min(f[i - 1][j+1][b] + x, f[i - 1][j][True] + 1)\n",
    "                    if j:  # 可以免费反转\n",
    "                        f[i][j][b]= min(f[i][j][b], f[i - 1][j-1][b])\n",
    "        return f[n - 1][0][False]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n=sum(x!=y for x,y in zip(s1,s2))\n",
    "        if n&1:return -1\n",
    "        a=[]\n",
    "        for i,(z,y) in enumerate(zip(s1,s2)):\n",
    "            if z!=y:\n",
    "                a.append(i)\n",
    "        @cache\n",
    "        def f(l,r):\n",
    "            if l>r:return 0\n",
    "            if r-l+1&1:return inf\n",
    "            ans=inf\n",
    "            for i in range(l+1,r+1):\n",
    "                d=a[i]-a[l]\n",
    "                if d>x:d=x\n",
    "                ans=min(ans,d+f(l+1,i-1)+f(i+1,r))\n",
    "            return ans\n",
    "        return f(0,n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        \n",
    "        n = len(s1)\n",
    "        diff = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]: diff.append(i)\n",
    "        \n",
    "        if len(diff) % 2 == 1: return -1\n",
    "        m = len(diff)\n",
    "        if m == 0: return 0\n",
    "        @cache\n",
    "        def getans(i, j):\n",
    "            if i == j: return inf\n",
    "            if i+1 == j: return min(diff[j] - diff[i], x)            \n",
    "            ans = min(diff[j] - diff[i], x) + getans(i+1, j-1)\n",
    "            for k in range(i+1, j):\n",
    "                ans = min(ans, getans(i, k) + getans(k+1, j))\n",
    "            return ans\n",
    "        \n",
    "        return getans(0, m-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count(\"1\") % 2 != s2.count(\"1\") % 2:\n",
    "            return -1\n",
    "        n = len(s1)\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, pre: bool) -> int:\n",
    "            if j > i+1:\n",
    "                return inf\n",
    "            if i < 0:\n",
    "                return inf if j or pre else 0\n",
    "            if (s1[i] == s2[i]) == (not pre):\n",
    "                return dfs(i-1, j, False)\n",
    "            res = min(dfs(i-1, j+1, False) + x, dfs(i-1, j, True) + 1)\n",
    "            if j > 0:\n",
    "                res = min(res, dfs(i-1, j-1, False))\n",
    "            return res\n",
    "        return dfs(n-1, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        d = []\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                d.append(i)\n",
    "                \n",
    "        if len(d) % 2 == 1:\n",
    "            return -1\n",
    "        \n",
    "        @cache\n",
    "        def dp(i, p, pre):\n",
    "            if i == len(d):\n",
    "                return p//2*x\n",
    "            if pre:\n",
    "                return min(min(d[i]-d[i-1], x) + dp(i+1, p-1, False), dp(i+1, p+1, True))\n",
    "            else:\n",
    "                return dp(i+1, p+1, True)\n",
    "        return dp(0, 0, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1, s2, x):\n",
    "        s, t = list(s1), list(s2)\n",
    "        n, diff = len(s), 0\n",
    "        for i in range(n):\n",
    "            diff ^= ord(s[i]) ^ ord(t[i])\n",
    "        if diff != 0:\n",
    "            return -1\n",
    "        memo = [[[-1 for _ in range(2)] for _ in range(n + 1)] for _ in range(n)]\n",
    "\n",
    "        def dfs(i, j, preRev):\n",
    "            if i < 0:\n",
    "                return j > 0 or preRev > 0 and float('inf') or 0\n",
    "            if memo[i][j][preRev] != -1:\n",
    "                return memo[i][j][preRev]\n",
    "            if (s[i] == t[i]) == (preRev == 0):\n",
    "                return dfs(i - 1, j, 0)\n",
    "            res = min(dfs(i - 1, j + 1, 0) + x, dfs(i - 1, j, 1) + 1)\n",
    "            if j > 0:\n",
    "                res = min(res, dfs(i - 1, j - 1, 0))\n",
    "            memo[i][j][preRev] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(n - 1, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count(\"1\") % 2 != s2.count(\"1\") % 2:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, preRev: bool) -> int:\n",
    "            if j > i > 0:\n",
    "                return math.inf\n",
    "            if i < 0:\n",
    "                # if j or preRev:  # 如果还能免费反转或者上一次进行了操作2，是不合法的\n",
    "                #     return math.inf\n",
    "                # return 0\n",
    "                return math.inf if j or preRev else 0\n",
    "            # if s1[i] == s2[i]:  # 如果该位置上两个一样，\n",
    "            #     if not preRev:  # 且上一次没有进行操作2\n",
    "            #         return dfs(i - 1, j, False)  # 带着一样的j直接进入下一个\n",
    "            # else :  # 如果该位置上两个不一样\n",
    "            #     if preRev:#但上一次进行了操作2，也就是该位置上已经反转\n",
    "            #         return dfs(i - 1, j, False)  # 也直接进入下一个\n",
    "            # 以上简写成：\n",
    "            if (s1[i] == s2[i]) == (not preRev):\n",
    "                return dfs(i - 1, j, False)\n",
    "\n",
    "            return min(dfs(i - 1, j, True) + 1,  # 采用操作2\n",
    "                       dfs(i - 1, j - 1, False) if j > 0 else math.inf,  # 免费反转\n",
    "                       dfs(i - 1, j + 1, False) + x,  # 采用操作1\n",
    "                       )\n",
    "\n",
    "        return dfs(len(s1) - 1, 0, False)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        diff=[]\n",
    "        for i,tmp in enumerate(s1):\n",
    "            if tmp!=s2[i]:\n",
    "                diff.append(i)\n",
    "        l=len(diff)\n",
    "        if l==0:\n",
    "            return 0\n",
    "        if l%2!=0:\n",
    "            return -1\n",
    "        dp=[[[int(1e9),int(1e9)] for j in range(l+1)] for i in range(l)]\n",
    "        dp[0][1][1]=0\n",
    "        for i in range(1,l):\n",
    "            for j in range(i+2):\n",
    "                if j+1<l:\n",
    "                    dp[i][j][0]=min( dp[i][j][0] , dp[i-1][j+1][1]+diff[i]-diff[i-1] )\n",
    "                \n",
    "                dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][1] )\n",
    "                dp[i][j][1]=min(dp[i][j][1], dp[i-1][j-1][0] )\n",
    "        ans=int(1e9)\n",
    "        for j in range(0,l+1,2):\n",
    "            for last in range(2):\n",
    "                ans=min(ans,dp[l-1][j][last]+x*(j//2))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = [i for i in range(n) if s1[i] != s2[i]]\n",
    "        m = len(a)\n",
    "\n",
    "        @cache\n",
    "        def g(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            if p == q:\n",
    "                return math.inf\n",
    "            if p == m-1:\n",
    "                return math.inf\n",
    "            ans = a[p+1] - a[p] + g(p+2, q)\n",
    "            if a[p+1] == a[p]+1:\n",
    "                return ans\n",
    "            for k in range(p+1, q+1):\n",
    "                if k-p >= 3 and (k-p) % 2 and a[k-1] - a[k-2] >= x:\n",
    "                    break\n",
    "                ans = min(ans, x + g(p+1, k-1) + g(k+1, q))\n",
    "            return ans\n",
    "        \n",
    "        ans = g(0, m-1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        assert 1 <= n <= 500 \n",
    "        assert n == len(s2)\n",
    "        for i in s1+s2:\n",
    "            assert i in \"01\"\n",
    "        \n",
    "        s = []\n",
    "        self.x = x\n",
    "        for i in range(n):\n",
    "            if s1[i] != s2[i]:\n",
    "                s.append(1)\n",
    "            else:\n",
    "                s.append(0)\n",
    "        \n",
    "        res = self.sea(tuple(s), 0) \n",
    "        if res >= 10**9:\n",
    "            return -1\n",
    "        return res\n",
    "    \n",
    "    @cache\n",
    "    def sea(self, s, flag):\n",
    "        origin_s = copy.copy(s)\n",
    "        s = list(s)\n",
    "        while s and s[-1] == 0:\n",
    "            s.pop() \n",
    "            \n",
    "        if not s :\n",
    "            if not flag:\n",
    "                return 0 \n",
    "            else:\n",
    "                return 10**9\n",
    "        \n",
    "        s.pop()\n",
    "        if 1 not in s:\n",
    "            if flag:\n",
    "                return 0\n",
    "            else:\n",
    "                return 10**9\n",
    "            \n",
    "        # 连续的\n",
    "        s[-1] = s[-1] ^ 1\n",
    "        res = self.sea(tuple(s), flag) + 1\n",
    "        \n",
    "        s[-1] = s[-1] ^ 1\n",
    "        \n",
    "        # 非连续\n",
    "        s = tuple(s)\n",
    "        if flag:\n",
    "            res = min(res, self.sea(s, 0))\n",
    "        else:\n",
    "            res = min(res, self.sea(s, 1) + self.x)\n",
    "        # print(origin_s, flag, res)\n",
    "        return res\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        a = [i for i in range(n) if s1[i] != s2[i]]\n",
    "        m = len(a)\n",
    "\n",
    "        @cache\n",
    "        def g(p, q):\n",
    "            if p > q:\n",
    "                return 0\n",
    "            if p == q:\n",
    "                return math.inf\n",
    "            if p == m-1:\n",
    "                return math.inf\n",
    "            ans = a[p+1] - a[p] + g(p+2, q)\n",
    "            if a[p+1] == a[p]+1:\n",
    "                return ans\n",
    "            for k in range(p+1, q+1):\n",
    "                ans = min(ans, x + g(p+1, k-1) + g(k+1, q))\n",
    "            return ans\n",
    "        \n",
    "        ans = g(0, m-1)\n",
    "        return ans if ans < math.inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, k: int) -> int:\n",
    "        n = len(s1)\n",
    "        cnt1 = cnt2 = 0\n",
    "        for x, y in zip(s1, s2):\n",
    "            cnt1 += int(x == '1')\n",
    "            cnt2 += int(y == '1')\n",
    "        if cnt1 % 2 != cnt2 % 2:\n",
    "            return -1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, p: int) -> int:\n",
    "            if i == -1:\n",
    "                return 0 if j == 0 and p == 0 else inf\n",
    "            # if (p == 0 and s1[i] == s2[i]) or (p == 1 and s1[i] != s2[i]):\n",
    "            #     return dfs(i - 1, j, 0)\n",
    "            if s1[i] == '0' and p == 0:\n",
    "                x = '0'\n",
    "            elif s1[i] == '0' and p == 1:\n",
    "                x = '1'\n",
    "            elif s1[i] == '1' and p == 0:\n",
    "                x = '1'\n",
    "            else:\n",
    "                x = '0' \n",
    "            if x == s2[i]:\n",
    "                return dfs(i - 1, j, 0)\n",
    "            if j > 0:\n",
    "                return min(dfs(i - 1, j - 1, 0), dfs(i - 1, j + 1, 0) + k, dfs(i - 1, j, 1) + 1)\n",
    "            return min(dfs(i - 1, j + 1, 0) + k, dfs(i - 1, j, 1) + 1)\n",
    "        return dfs(n - 1, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i, j, prev):\n",
    "            if i == -1:\n",
    "                return 0\n",
    "            if s1[i] == s2[i] and not prev:\n",
    "                return dfs(i - 1, j, False)\n",
    "            if s1[i] != s2[i] and prev:\n",
    "                return dfs(i - 1, j, False)\n",
    "            \n",
    "            res = inf\n",
    "            if j > 0:\n",
    "                res = min(res, dfs(i - 1, j - 1, False))\n",
    "            if i > 0:\n",
    "                res = min(res, dfs(i - 1, j, True) + 1)\n",
    "                res = min(res, dfs(i - 1, j + 1, False) + x)\n",
    "            return res\n",
    "        \n",
    "        return dfs(len(s1) - 1, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        \n",
    "        if s1.count('1') % 2 != s2.count('1') % 2:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, pre_rev: bool) -> int:\n",
    "            if i < 0:\n",
    "                return inf if j or pre_rev else 0\n",
    "            if (s1[i] == s2[i]) == (not pre_rev):  # 无需反转\n",
    "                return dfs(i - 1, j, False)\n",
    "            res = min(dfs(i - 1, j + 1, False) + x, dfs(i - 1, j, True) + 1)\n",
    "            if j:  # 可以免费反转\n",
    "                res = min(res, dfs(i - 1, j - 1, False))\n",
    "            return res\n",
    "        return dfs(len(s1) - 1, 0, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        if s1.count('1')%2!=s2.count('1')%2:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dsf(idx,if_pre,jun_num):\n",
    "            if idx<0:\n",
    "                if not if_pre and not jun_num:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    return inf\n",
    "            # 可以直接跳到下一个的情况,不需要进行判断\n",
    "            if (s1[idx]==s2[idx])==(not if_pre):\n",
    "                return dsf(idx-1,False,jun_num)\n",
    "            res0 = dsf(idx-1,True,jun_num)+1\n",
    "            res1 = dsf(idx-1,False,jun_num+1)+x\n",
    "            res = min(res0,res1)\n",
    "            if jun_num>0:\n",
    "                res = min(res,dsf(idx-1,False,jun_num-1))\n",
    "            return res\n",
    "\n",
    "        return dsf(n-1,False,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        if s1.count('1')%2!=s2.count('1')%2:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dsf(idx,if_pre,jun_num):\n",
    "            if idx<0:\n",
    "                if not if_pre and not jun_num:\n",
    "                    return 0 \n",
    "                else:\n",
    "                    return inf\n",
    "            # 可以直接跳到下一个的情况,不需要进行判断 对res 和jun_num没有任何变化，且是最优选择方式\n",
    "            if (s1[idx]==s2[idx])==(not if_pre):\n",
    "                return dsf(idx-1,False,jun_num)\n",
    "            # 需要判断的部分，不确定的部分无论s1[idx]和s2[idx]是否相等都要试\n",
    "            res = dsf(idx-1,True,jun_num)+1 #第二种方式\n",
    "            if s1[idx]!=s2[idx]:\n",
    "                res1 = dsf(idx-1,False,jun_num+1)+x #第一种方式\n",
    "                res = min(res,res1)\n",
    "            if jun_num>0: #消耗免费次数\n",
    "                res = min(res,dsf(idx-1,False,jun_num-1))\n",
    "            return res\n",
    "\n",
    "        return dsf(n-1,False,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        n = len(s1)\n",
    "        # 如果不同的位置个数为奇数则一定不能相等可以先进行判断\n",
    "        cnt = 0\n",
    "        for i,j in enumerate(s1):\n",
    "            cnt += j != s2[i]\n",
    "        if cnt&1:\n",
    "            return -1\n",
    "        if x == 1:\n",
    "            return cnt>>1\n",
    "        # 难道非要记录那些位置换没换吗？\n",
    "        @cache\n",
    "        def dfs(cur=0,cnt=0,hasChange=False):\n",
    "            if cur == n:\n",
    "                return 0\n",
    "            if (s1[cur] == s2[cur]) == (not hasChange):\n",
    "                return dfs(cur+1,cnt,False)\n",
    "            ans = dfs(cur+1,cnt+1,False)+x\n",
    "            ans = min(ans,dfs(cur+1,cnt,True)+1)\n",
    "            if cnt:\n",
    "                ans = min(ans,dfs(cur+1,cnt-1,False))\n",
    "            return ans\n",
    "        return dfs()\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s1: str, s2: str, x: int) -> int:\n",
    "        if Counter(s1)['1'] % 2 != Counter(s2)['1'] % 2:\n",
    "            return -1\n",
    "\n",
    "        i = 0\n",
    "        n = len(s1)\n",
    "        '''\n",
    "        i=字符\n",
    "        free=有几次免费反转的机会\n",
    "        preRev=上一个字符翻转\n",
    "        '''\n",
    "        @cache\n",
    "        def dfs(i, free, preRev):\n",
    "            if free < 0:\n",
    "                return inf\n",
    "            \n",
    "            if i == n:\n",
    "                if free == 0 and not preRev:\n",
    "                    return 0\n",
    "                else:\n",
    "                    return inf\n",
    "            \n",
    "            '''\n",
    "            什么都不做\n",
    "            '''\n",
    "            if s1[i] == s2[i] and not preRev:\n",
    "                return dfs(i+1, free, False)\n",
    "\n",
    "            if s1[i] != s2[i] and preRev:\n",
    "                return dfs(i+1, free, False)\n",
    "            \n",
    "            # 第i个位置不相等\n",
    "            if (s1[i] != s2[i] and not preRev) or (s1[i] == s2[i] and preRev):\n",
    "                return min(dfs(i+1, free-1, False), dfs(i+1, free+1, False)+x, dfs(i+1,free,True)+1)\n",
    "            \n",
    "\n",
    "        return dfs(0,0,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        cnt, x = 0, 0\n",
    "        for c in s:\n",
    "            i = int(c)\n",
    "            cnt += i^x\n",
    "            x = 1-x\n",
    "        return min(cnt, l-cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        ls = list(s)\n",
    "        res1 = 0\n",
    "        for i in range(len(ls)):\n",
    "            if i % 2 == 0:\n",
    "                if ls[i] == '1':\n",
    "                    res1 += 1\n",
    "            else:\n",
    "                if ls[i] == '0':\n",
    "                    res1 += 1\n",
    "        return min(res1, len(ls)-res1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) == i & 1 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        a=b=0\n",
    "        for i in range(len(s)):\n",
    "            if (i%2==0 and 1-int(s[i])==1) or (i%2==1 and 1-int(s[i])==0):\n",
    "                a+=1\n",
    "            else:\n",
    "                b+=1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if int(s[i]) != i % 2:\n",
    "                ans += 1\n",
    "        return min(ans, n - ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, cnt1 = '0', 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "        return min(cnt1, n - cnt1)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        count1=0\n",
    "        count2=0\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            if i%2==0 and s[i]=='1':\n",
    "                count1+=1\n",
    "            if i%2!=0 and s[i]=='0':\n",
    "                count1+=1\n",
    "            if i%2!=0 and s[i]=='1':\n",
    "                count2+=1\n",
    "            if i%2==0 and s[i]=='0':\n",
    "                count2+=1\n",
    "        return min(count1,count2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if s[0] == '1':\n",
    "            cnt1 += 1\n",
    "\n",
    "        if s[0] == '0':\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        sum = 0\n",
    "        for ind, num in enumerate(s):\n",
    "            sum += int(num) == ind % 2\n",
    "        return min(sum, len(s)-sum)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, cnt1 = '0', 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "        return min(cnt1, n - cnt1)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        cnt, x = 0, 0\n",
    "        for c in s:\n",
    "            i = int(c)\n",
    "            cnt += i^x\n",
    "            x = 1-x\n",
    "        return min(cnt, l-cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        n0 = n1 = 0\n",
    "        c0 = '0'\n",
    "        c1 = '1'\n",
    "        for c in s:\n",
    "            if c != c0:\n",
    "                n0 += 1\n",
    "            if c0 == '0':\n",
    "                c0 = '1'\n",
    "            else:\n",
    "                c0 = '0'\n",
    "            \n",
    "            if c != c1:\n",
    "                n1 += 1\n",
    "            if c1 == '0':\n",
    "                c1 = '1'\n",
    "            else:\n",
    "                c1 = '0'\n",
    "        \n",
    "        return min(n0, n1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        count1=0\n",
    "        count2=0\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            if i%2==0 and s[i]=='1':\n",
    "                count1+=1\n",
    "            if i%2!=0 and s[i]=='0':\n",
    "                count1+=1\n",
    "        for i in range(n):\n",
    "            if i%2!=0 and s[i]=='1':\n",
    "                count2+=1\n",
    "            if i%2==0 and s[i]=='0':\n",
    "                count2+=1\n",
    "        return min(count1,count2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        s1, s2 = '', ''\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            s1 = \"01\" * (n // 2)\n",
    "            s2 = \"10\" * (n // 2)\n",
    "        else:\n",
    "            s1 = \"01\" * (n // 2) + '0'\n",
    "            s2 = \"10\" * (n // 2) + '1'\n",
    "\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if s[i] != s1[i]:\n",
    "                cnt1 += 1\n",
    "            \n",
    "            if s[i] != s2[i]:\n",
    "                cnt2 += 1\n",
    "                \n",
    "        return min(cnt1, cnt2)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        操作数1 = 操作数2 = 0\n",
    "        标记 = \"0\"\n",
    "        for i in s:\n",
    "            if i == 标记:\n",
    "                操作数1 += 1\n",
    "            else:\n",
    "                操作数2 += 1\n",
    "            标记 = \"0\" if 标记 == \"1\" else \"1\"\n",
    "        return min(操作数1, 操作数2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        test1 = 0\n",
    "        test2 = 0\n",
    "        for i in range(len(s)):\n",
    "            if i % 2 == 0:\n",
    "                if s[i] != \"0\":\n",
    "                    test1 += 1\n",
    "                else:\n",
    "                    test2 += 1\n",
    "            else:\n",
    "                if s[i] != \"1\":\n",
    "                    test1 += 1\n",
    "                else:\n",
    "                    test2 += 1\n",
    "        return min(test1, test2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        a=0\n",
    "        b=0\n",
    "        if len(s)%2!=0:\n",
    "            x = '10'*(len(s)//2)+'1'\n",
    "            y = '01'*(len(s)//2)+'0'\n",
    "        else:\n",
    "            x = '10'*(len(s)//2)\n",
    "            y = '01'*(len(s)//2)\n",
    "        for i,j in enumerate(s):\n",
    "            if s[i]!=x[i]:\n",
    "                a+=1\n",
    "            if s[i]!=y[i]:\n",
    "                b+=1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        d = list(s)\n",
    "        l = len(s)\n",
    "        if len(s)%2 == 0:\n",
    "            c = ['10'*int(l/2)]\n",
    "            b = ['01'*int(l/2)]\n",
    "            e = 0\n",
    "            f = 0\n",
    "            for i in range(0,len(d)):\n",
    "                if c[0][i] != d[i]:\n",
    "                    e += 1\n",
    "                elif b[0][i] != d[i]:\n",
    "                    f += 1\n",
    "        else:\n",
    "            c = ['10' * int(l / 2)+'1']\n",
    "            b = ['01' * int(l / 2)+'0']\n",
    "            e = 0\n",
    "            f = 0\n",
    "            for i in range(0,len(d)):\n",
    "                if c[0][i] != d[i]:\n",
    "                    e += 1\n",
    "                elif b[0][i] != d[i]:\n",
    "                    f += 1\n",
    "        return min(e,f)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        ans1, ans2 = 0, 1\n",
    "        first = s[0]\n",
    "        for i in range(1, len(s)):\n",
    "            if i % 2 != 0:\n",
    "                if s[i] == first:\n",
    "                    ans1 += 1\n",
    "                else:\n",
    "                    ans2 += 1\n",
    "            else:\n",
    "                if s[i] != first:\n",
    "                    ans1 += 1\n",
    "                else:\n",
    "                    ans2 += 1\n",
    "\n",
    "        return min(ans1, ans2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            if int(s[i]) != i % 2:\n",
    "                ans += 1\n",
    "        return min(ans, n - ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) == i%2 for i,c in enumerate(s))\n",
    "        return min(cnt,len(s)-cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        cao = 0\n",
    "\n",
    "        for i,v in enumerate(s):\n",
    "            if i%2 == 1:\n",
    "                if v != '1':\n",
    "                    ans+=1\n",
    "            if i%2 == 0:\n",
    "                if v!='0':\n",
    "                    ans+=1\n",
    "        for i,v in enumerate(s):\n",
    "            if i%2 == 1:\n",
    "                if v != '0':\n",
    "                    cao+=1\n",
    "            if i%2 == 0:\n",
    "                if v!='1':\n",
    "                    cao+=1\n",
    "        return min(ans,cao)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        res1,res2 = 0,0\n",
    "        cnt = 0\n",
    "        for i in s:\n",
    "            if cnt % 2:\n",
    "                if i == '0':res1 += 1\n",
    "                else:res2 += 1\n",
    "            else:\n",
    "                if i == '1':res1 += 1\n",
    "                else:res2 += 1\n",
    "            cnt += 1\n",
    "        return min(res1,res2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        n, cnt = len(s), 0\n",
    "        for i, c in enumerate(s):\n",
    "            if i % 2 == 0:\n",
    "                if c != '0':\n",
    "                    cnt += 1\n",
    "            else:\n",
    "                if c != '1':\n",
    "                    cnt += 1\n",
    "        return min(cnt, n-cnt)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        n =len(s)\n",
    "        p = ['0','1']\n",
    "        idx = 0\n",
    "        cnt_0 = 0\n",
    "        for j in range(n):\n",
    "            if s[j]!=p[idx%2]:\n",
    "                cnt_0+=1\n",
    "            idx +=1\n",
    "        idx = 1\n",
    "        cnt_1 = 0\n",
    "        for j in range(n):\n",
    "            if s[j]!=p[idx%2]:\n",
    "                cnt_1+=1\n",
    "            idx +=1\n",
    "        return min(cnt_0,cnt_1)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(c != \"01\"[i&1] for i, c in enumerate(s))\n",
    "        return min(cnt, len(s)-cnt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        操作数1 = 操作数2 = 0\n",
    "        标记 = \"0\"\n",
    "        for i in s:\n",
    "            if i == 标记:\n",
    "                操作数1 += 1\n",
    "            else:\n",
    "                操作数2 += 1\n",
    "            标记 = \"0\" if 标记 == \"1\" else \"1\"\n",
    "        return min(操作数1, 操作数2)\n",
    "        \"\"\"\n",
    "        #优化\n",
    "        操作数 = sum(int(j) == i%2 for i, j in enumerate(s))\n",
    "        return min(操作数, len(s)-操作数)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        count1 = 0\n",
    "        count2 = 0\n",
    "        tag = True\n",
    "        for char in s:\n",
    "            if tag:\n",
    "                if(char != '0'):\n",
    "                    count1 += 1\n",
    "            else:\n",
    "                if(char != '1'):\n",
    "                    count1 += 1\n",
    "            tag = not tag\n",
    "        tag = True\n",
    "        for char in s:\n",
    "            if tag:\n",
    "                if(char != '1'):\n",
    "                    count2 += 1\n",
    "            else:\n",
    "                if(char != '0'):\n",
    "                    count2 += 1\n",
    "            tag = not tag\n",
    "        return count1 if count1 < count2 else count2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        s1, s2 = '', ''\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            s1 = \"01\" * (n // 2)\n",
    "            s2 = \"10\" * (n // 2)\n",
    "        else:\n",
    "            s1 = \"01\" * (n // 2) + '0'\n",
    "            s2 = \"10\" * (n // 2) + '1'\n",
    "\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if s[i] != s1[i]:\n",
    "                cnt1 += 1\n",
    "            \n",
    "            if s[i] != s2[i]:\n",
    "                cnt2 += 1\n",
    "                \n",
    "        return min(cnt1, cnt2)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s) - cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        z1 = ['0' if i%2==0 else '1' for i in range(len(s))]\n",
    "        su = 0\n",
    "        for i in range(len(s)):\n",
    "            su += 1 if s[i]!=z1[i] else 0\n",
    "        return min(su,len(s)-su)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if s[0] == '1':\n",
    "            cnt1 += 1\n",
    "\n",
    "        if s[0] == '0':\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        res = sum(1 for i, j in enumerate(s) if int(j) == i % 2)\n",
    "        return min(res, len(s) - res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        ret = 10 ** 9\n",
    "        for k in '01':\n",
    "            cnt = 0\n",
    "            for i in range(len(s)):\n",
    "                if i & 1 == 0 and s[i] == k:\n",
    "                    cnt += 1\n",
    "                elif i & 1 and s[i] != k:\n",
    "                    cnt += 1\n",
    "            ret = min(ret, cnt)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        zero = one = 0  # 0或1开头的情况需要更改的数量\n",
    "        for i, c in enumerate(s):\n",
    "            if (i & 1) ^ (c == '1'):\n",
    "                zero += 1\n",
    "            else:\n",
    "                one += 1\n",
    "        return min(zero, one)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        ls = list(s)\n",
    "        res1, res2 = 0, 0\n",
    "        for i in range(len(ls)):\n",
    "            if i % 2 == 0:\n",
    "                if ls[i] == '1':\n",
    "                    res1 += 1\n",
    "                else:\n",
    "                    res2 += 1\n",
    "            else:\n",
    "                if ls[i] == '0':\n",
    "                    res1 += 1\n",
    "                else:\n",
    "                    res2 += 1\n",
    "        return min(res1, res2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        cnt = sum(int(c) != i % 2 for i, c in enumerate(s))\n",
    "        return min(cnt, len(s)-cnt)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        ls = list(s)\n",
    "        res1 = 0\n",
    "        for i in range(len(ls)):\n",
    "            if i % 2 == 0:\n",
    "                if ls[i] == '1':\n",
    "                    res1 += 1\n",
    "            else:\n",
    "                if ls[i] == '0':\n",
    "                    res1 += 1\n",
    "        return min(res1, len(ls)-res1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if s[0] == '1':\n",
    "            cnt1 += 1\n",
    "\n",
    "        if s[0] == '0':\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        a=b=0\n",
    "        for i in range(len(s)):\n",
    "            if (i%2==0 and 1-int(s[i])==1) or (i%2==1 and 1-int(s[i])==0):\n",
    "                a+=1\n",
    "            else:\n",
    "                b+=1\n",
    "        return min(a,b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, cnt1 = '0', 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "        return min(cnt1, n - cnt1)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        odd = n // 2\n",
    "        even = n - odd \n",
    "        odd_1 = len([s[i] for i in range(1, n, 2) if s[i] == \"1\"])\n",
    "        odd_0 = len([s[i] for i in range(1, n, 2) if s[i] == \"0\"])\n",
    "        even_1 = len([s[i] for i in range(0, n, 2) if s[i] == \"1\"])\n",
    "        even_0 = len([s[i] for i in range(0, n, 2) if s[i] == \"0\"])\n",
    "        return min(odd - odd_1 + even - even_0, odd - odd_0 + even - even_1) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        ans = sum([int(c) == (i % 2) for i, c in enumerate(s)])\n",
    "        return min(ans, len(s) - ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        \"\"\"\n",
    "        操作数1 = 操作数2 = 0\n",
    "        标记 = \"0\"\n",
    "        for i in s:\n",
    "            if i == 标记:\n",
    "                操作数1 += 1\n",
    "            else:\n",
    "                操作数2 += 1\n",
    "            标记 = \"0\" if 标记 == \"1\" else \"1\"\n",
    "        return min(操作数1, 操作数2)\n",
    "        \"\"\"\n",
    "        #优化\n",
    "        操作数 = sum(int(j) == i%2 for i, j in enumerate(s))\n",
    "        return min(操作数, len(s)-操作数)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        ans1, ans2, cnt1, cnt2 = '0', '1', 0, 0\n",
    "\n",
    "        if ans1 != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2 != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "\n",
    "            if s[i] == ans1:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1 = '1'\n",
    "                else:\n",
    "                    ans1 = '0'\n",
    "            else:\n",
    "                ans1 = s[i]\n",
    "\n",
    "            if s[i] == ans2:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2 = '1'\n",
    "                else:\n",
    "                    ans2 = '0'\n",
    "            else:\n",
    "                ans2 = s[i]\n",
    "\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        min0=min(len([x for x in range(0,len(s),2) if s[x]=='0']),len([x for x in range(1,len(s),2) if s[x]=='0']))\n",
    "        min1=min(len([x for x in range(0,len(s),2) if s[x]=='1']),len([x for x in range(1,len(s),2) if s[x]=='1']))\n",
    "        return min0+min1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        k = len(s)\n",
    "        su = 0\n",
    "        z1 = ['0' if i%2==0 else '1' for i in range(k)]\n",
    "        for i in range(k):\n",
    "            su += 1 if s[i]!=z1[i] else 0\n",
    "        return min(su,len(s)-su)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        s1, s2 = '', ''\n",
    "\n",
    "        if n % 2 == 0:\n",
    "            s1 = \"01\" * (n // 2)\n",
    "            s2 = \"10\" * (n // 2)\n",
    "        else:\n",
    "            s1 = \"01\" * (n // 2) + '0'\n",
    "            s2 = \"10\" * (n // 2) + '1'\n",
    "\n",
    "        cnt1, cnt2 = 0, 0\n",
    "        for i in range(n):\n",
    "            if s[i] != s1[i]:\n",
    "                cnt1 += 1\n",
    "            \n",
    "            if s[i] != s2[i]:\n",
    "                cnt2 += 1\n",
    "                \n",
    "        return min(cnt1, cnt2)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        d = len(s)\n",
    "        if d % 2 == 0:\n",
    "            a = d // 2\n",
    "            b = 0\n",
    "        else:\n",
    "            a = d // 2 \n",
    "            b = 1\n",
    "        b1 = \"\".join([\"01\" for _ in range(a)] + [\"0\" * b])\n",
    "        b2 = \"\".join([\"10\" for _ in range(a)] + [\"1\" * b])\n",
    "        result1 = 0\n",
    "        result2 = 0\n",
    "        for i in range(d):\n",
    "            if s[i] != b1[i]:\n",
    "                result1 +=1\n",
    "            else:\n",
    "                result2 += 1\n",
    "        return min(result1,result2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        string = \"01\"\n",
    "        ans = sum([1 for index, ch in enumerate(s) if ch != string[index & 1]])\n",
    "        return min(ans, len(s) - ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        # 列表长度\n",
    "        length = len(s)\n",
    "        # 全0或全1情况\n",
    "        if s.count(\"1\") == 0 or s.count(\"1\") == length:\n",
    "            return length // 2\n",
    "        # 如果长度是偶数\n",
    "        if length % 2 == 0:\n",
    "            need_str_01 = \"10\" * (length // 2)\n",
    "            need_str_02 = \"01\" * (length // 2)\n",
    "            revert_01 = 0\n",
    "            revert_02 = 0\n",
    "            for i in range(length):\n",
    "                if need_str_01[i] != s[i]:\n",
    "                    revert_01 += 1\n",
    "                if need_str_02[i] != s[i]:\n",
    "                    revert_02 += 1\n",
    "        else:\n",
    "            need_str_01 = \"10\" * (length // 2) + \"1\"\n",
    "            need_str_02 = \"01\" * (length // 2) + \"0\"\n",
    "            revert_01 = 0\n",
    "            revert_02 = 0\n",
    "            for i in range(length):\n",
    "                if need_str_01[i] != s[i]:\n",
    "                    revert_01 += 1\n",
    "                if need_str_02[i] != s[i]:\n",
    "                    revert_02 += 1\n",
    "        print(revert_01, revert_02)\n",
    "        return min(revert_01, revert_02)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        string = \"01\" * (len(s) // 2) + (\"0\" if len(s) & 1 else \"\")\n",
    "        ans = sum([1 for index, ch in enumerate(s) if ch != string[index]])\n",
    "        return min(ans, len(s) - ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        return min(sum([int(s[a]) != (a%2) for a in range(len(s))]), sum([int(s[a]) != ((a+1)%2) for a in range(len(s))]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        z1 = ['0' if i%2==0 else '1' for i in range(len(s))]\n",
    "        z2 = ['1' if i%2==0 else '0' for i in range(len(s))]\n",
    "        su = 0\n",
    "        sm = 0\n",
    "        for i in range(len(s)):\n",
    "            su += 1 if s[i]!=z1[i] else 0\n",
    "            sm += 1 if s[i]!=z2[i] else 0\n",
    "        return min(su,sm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        # 对一个长度为4的字符串，交替字符串的形式只有两种 1010 或0101，只需要将原始字符串与目标字符串进行比较\n",
    "\n",
    "        string1 = [\"1\" if i%2==1 else \"0\" for i in range(len(s))]\n",
    "        string2 = [\"1\" if i%2==0 else \"0\" for i in range(len(s))]\n",
    "\n",
    "        return min([i!=j for i, j in zip(string1, list(s))].count(True), [i!=j for i, j in zip(string2, list(s))].count(True))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def shengchengzifu(n):\n",
    "            s1 = [\"0\" if i%2==0 else \"1\" for i in range(1,n+1)]\n",
    "            s2 = [\"1\" if i%2==0 else \"0\" for i in range(1,n+1)]\n",
    "            return [\"\".join(s1),\"\".join(s2)]\n",
    "        res = shengchengzifu(n)\n",
    "        print(res)\n",
    "        def jisuanbutong(s1,s2):\n",
    "            count = 0\n",
    "            for i in range(len(s1)):\n",
    "                if s1[i]!=s2[i]:\n",
    "                    count+=1\n",
    "            return count\n",
    "        r = min(jisuanbutong(s,res[0]),jisuanbutong(s,res[1]))\n",
    "        return (r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, s: str) -> int:\n",
    "\n",
    "        ans1, ans2, cnt1, cnt2 = ['0'], ['1'], 0, 0\n",
    "\n",
    "        if ans1[0] != s[0]:\n",
    "            cnt1 += 1\n",
    "\n",
    "        if ans2[0] != s[0]:\n",
    "            cnt2 += 1\n",
    "\n",
    "        for i in range(1, len(s)):\n",
    "\n",
    "            if s[i] == ans1[-1]:\n",
    "                cnt1 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans1.append('1')\n",
    "                else:\n",
    "                    ans1.append('0')\n",
    "            else:\n",
    "                ans1.append(s[i])\n",
    "\n",
    "\n",
    "            if s[i] == ans2[-1]:\n",
    "                cnt2 += 1\n",
    "\n",
    "                if s[i] == '0':\n",
    "                    ans2.append('1')\n",
    "                else:\n",
    "                    ans2.append('0')\n",
    "            else:\n",
    "                ans2.append(s[i])\n",
    "\n",
    "        print(ans1, ans2)\n",
    "        return min(cnt1, cnt2)\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        print(ans2)\n",
    "        return min(cnt1, cnt2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        stack_num = []\n",
    "        stack_ops = []\n",
    "\n",
    "        def op_and(x1,y1,x2,y2):\n",
    "            return min(x1+y2,x2+y1,x1+x2), y1+y2\n",
    "        def op_or(x1,y1,x2,y2):\n",
    "            return x1+x2, min(x1+y2,x2+y1,y1+y2)\n",
    "        \n",
    "        def calc():\n",
    "            if len(stack_num)>=2 and stack_ops[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                x_and, y_and = op_and(x1,y1,x2,y2)\n",
    "                x_or, y_or = op_or(x1,y1,x2,y2)\n",
    "                op = stack_ops.pop()\n",
    "                if op=='&':\n",
    "                    stack_num.append((min(x_and,x_or+1),min(y_and,y_or+1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or,x_and+1),min(y_or,y_and+1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in ['(',\"|\",\"&\"]:\n",
    "                stack_ops.append(ch)\n",
    "            elif ch==\")\":\n",
    "                stack_ops.pop()\n",
    "                calc()\n",
    "            else:\n",
    "                if ch ==\"1\":\n",
    "                    stack_num.append((1,0))\n",
    "                    calc()\n",
    "                elif ch ==\"0\":\n",
    "                    stack_num.append((0,1))\n",
    "                    calc()\n",
    "        return max(stack_num[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        states = []\n",
    "        ops = []\n",
    "                \n",
    "        for c in expression:\n",
    "            if c in '01)':\n",
    "                if c == '0':\n",
    "                    states.append((0, 1))\n",
    "                elif c == '1':\n",
    "                    states.append((1, 0))\n",
    "                else:\n",
    "                    assert(ops[-1] == '(')\n",
    "                    ops.pop()\n",
    "                    \n",
    "                if len(ops) > 0 and ops[-1] != '(':\n",
    "                    op = ops.pop()\n",
    "                    p2, q2 = states.pop()\n",
    "                    p1, q1 = states.pop()\n",
    "                    if op == '&':\n",
    "                        states.append((min(p1, p2), min(q1 + q2, 1 + min(q1, q2))))\n",
    "                    else:\n",
    "                        states.append((min(p1 + p2, 1 + min(p1, p2)), min(q1, q2)))\n",
    "            else:\n",
    "                ops.append(c)\n",
    "        \n",
    "        return max(states[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        # 数字栈\n",
    "        stack_num = list()\n",
    "        # 符号栈\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return min(x1 + x2, x1 + y2, y1 + x2), y1 + y2\n",
    "\n",
    "        def op_or(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return x1 + x2, min(x1 + y2, y1 + x2, y1 + y2)\n",
    "        \n",
    "        # 尝试将数字栈顶的两个二元组和符号栈顶的运算符进行运算\n",
    "        def calc():\n",
    "            if len(stack_num) >= 2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                \n",
    "                x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "                x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "                if (op := stack_op.pop()) == \"&\":\n",
    "                    stack_num.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or, x_and + 1), min(y_or, y_and + 1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch == \"0\":\n",
    "                stack_num.append((0, 1))\n",
    "                calc()\n",
    "            elif ch == \"1\":\n",
    "                stack_num.append((1, 0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch == \")\"\n",
    "                # 此时符号栈栈顶一定是左括号\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "\n",
    "        return max(stack_num[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        nums = []\n",
    "        ops = []\n",
    "\n",
    "        def op_and(x1, y1, x2, y2):\n",
    "            x = min(x1 + x2, x1 + y2, x2 + y1)\n",
    "            y = y1 + y2\n",
    "\n",
    "            return x, y\n",
    "\n",
    "        def op_or(x1, y1, x2, y2):\n",
    "            x = x1 + x2\n",
    "            y = min(y1 + y2, x1 + y2, x2 + y1)\n",
    "\n",
    "            return x, y\n",
    "\n",
    "        def calc():\n",
    "            x1, y1 = nums.pop()\n",
    "            x2, y2 = nums.pop()\n",
    "            op = ops.pop()\n",
    "\n",
    "            x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "            x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "            if op == '&':\n",
    "                nums.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "            else:\n",
    "                nums.append((min(x_and + 1, x_or), min(y_and + 1, y_or)))\n",
    "\n",
    "        for i, t in enumerate(expression):\n",
    "            if t == '(':\n",
    "                ops.append('(')\n",
    "            elif t == ')':\n",
    "                while ops and ops[-1] != '(':\n",
    "                    calc()\n",
    "\n",
    "                if ops and ops[-1] == '(':\n",
    "                    ops.pop()\n",
    "\n",
    "            elif t in ('0', '1'):\n",
    "                if t == '0':\n",
    "                    nums.append((0, 1))\n",
    "                else:\n",
    "                    nums.append((1, 0))\n",
    "\n",
    "            else:\n",
    "                while ops and ops[-1] != '(':\n",
    "                    calc()\n",
    "                \n",
    "                ops.append(t)\n",
    "\n",
    "        while ops:\n",
    "            calc()\n",
    "\n",
    "        return max(nums[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        states = []\n",
    "        ops = []\n",
    "                \n",
    "        for c in expression:\n",
    "            if c in '01)':\n",
    "                if c == '0':\n",
    "                    states.append((0, 1))\n",
    "                elif c == '1':\n",
    "                    states.append((1, 0))\n",
    "                else:\n",
    "                    assert(ops[-1] == '(')\n",
    "                    ops.pop()\n",
    "                    \n",
    "                if len(ops) > 0 and ops[-1] != '(':\n",
    "                    op = ops.pop()\n",
    "                    p2, q2 = states.pop()\n",
    "                    p1, q1 = states.pop()\n",
    "                    if op == '&':\n",
    "                        states.append((min(p1, p2), min(q1 + q2, 1 + min(q1, q2))))\n",
    "                    else:\n",
    "                        states.append((min(p1 + p2, 1 + min(p1, p2)), min(q1, q2)))\n",
    "            else:\n",
    "                ops.append(c)\n",
    "        \n",
    "        return max(states[-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "\n",
    "\n",
    "        stack_num = list()\n",
    "        # 符号栈\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return min(x1 + x2, x1 + y2, y1 + x2), y1 + y2\n",
    "\n",
    "        def op_or(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return x1 + x2, min(x1 + y2, y1 + x2, y1 + y2)\n",
    "        \n",
    "        # 尝试将数字栈顶的两个二元组和符号栈顶的运算符进行运算\n",
    "        def calc():\n",
    "            if len(stack_num) >= 2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                \n",
    "                x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "                x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "                if (op := stack_op.pop()) == \"&\":\n",
    "                    stack_num.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or, x_and + 1), min(y_or, y_and + 1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch == \"0\":\n",
    "                stack_num.append((0, 1))\n",
    "                calc()\n",
    "            elif ch == \"1\":\n",
    "                stack_num.append((1, 0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch == \")\"\n",
    "                # 此时符号栈栈顶一定是左括号\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "\n",
    "        return max(stack_num[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "        stack_num = list()\n",
    "        # 符号栈\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return min(x1 + x2, x1 + y2, y1 + x2), y1 + y2\n",
    "\n",
    "        def op_or(x1: int, y1: int, x2: int, y2: int) -> (int, int):\n",
    "            return x1 + x2, min(x1 + y2, y1 + x2, y1 + y2)\n",
    "        \n",
    "        # 尝试将数字栈顶的两个二元组和符号栈顶的运算符进行运算\n",
    "        def calc():\n",
    "            if len(stack_num) >= 2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1, y1 = stack_num.pop()\n",
    "                x2, y2 = stack_num.pop()\n",
    "                \n",
    "                x_and, y_and = op_and(x1, y1, x2, y2)\n",
    "                x_or, y_or = op_or(x1, y1, x2, y2)\n",
    "\n",
    "                if (op := stack_op.pop()) == \"&\":\n",
    "                    stack_num.append((min(x_and, x_or + 1), min(y_and, y_or + 1)))\n",
    "                else:\n",
    "                    stack_num.append((min(x_or, x_and + 1), min(y_or, y_and + 1)))\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch == \"0\":\n",
    "                stack_num.append((0, 1))\n",
    "                calc()\n",
    "            elif ch == \"1\":\n",
    "                stack_num.append((1, 0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch == \")\"\n",
    "                # 此时符号栈栈顶一定是左括号\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "\n",
    "        return max(stack_num[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperationsToFlip(self, expression: str) -> int:\n",
    "\n",
    "        stack_num = list()\n",
    "        stack_op = list()\n",
    "\n",
    "        def op_and(x1, y1, x2,y2):\n",
    "            return min(x1+x2, x1+y2,y1+x2), y1+y2 \n",
    "        \n",
    "        def op_or(x1, y1,x2,y2):\n",
    "            return x1+x2, min(y1+y2, y1+x2, x1+y2)\n",
    "        \n",
    "        def calc():\n",
    "            if len(stack_num)>=2 and stack_op[-1] in [\"|\", \"&\"]:\n",
    "                x1,y1 = stack_num.pop()\n",
    "                x2,y2 = stack_num.pop()\n",
    "\n",
    "                x_and, y_and = op_and(x1,y1, x2,y2)\n",
    "                x_or, y_or = op_or(x1,y1,x2,y2)\n",
    "\n",
    "                opx = stack_op.pop()\n",
    "                if opx==\"&\":\n",
    "                    x_and, y_and = min(x_and, x_or+1), min(y_and,y_or+1)\n",
    "                    stack_num.append((x_and,y_and))\n",
    "                \n",
    "                elif opx==\"|\":\n",
    "                    x_or, y_or = min(x_or, x_and+1), min(y_or, y_and+1)\n",
    "                    stack_num.append((x_or,y_or))\n",
    "        \n",
    "        for ch in expression:\n",
    "            if ch in [\"(\", \"|\", \"&\"]:\n",
    "                stack_op.append(ch)\n",
    "            elif ch==\"0\":\n",
    "                stack_num.append( (0,1) )\n",
    "                calc()\n",
    "            elif ch==\"1\":\n",
    "                stack_num.append((1,0))\n",
    "                calc()\n",
    "            else:\n",
    "                assert ch==\")\"\n",
    "                stack_op.pop()\n",
    "                calc()\n",
    "        return max(stack_num[0])\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        res = numsDivide[0]\n",
    "        for num in numsDivide:\n",
    "            res = gcd(res, num)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        factor = [nums[i] for i in range(n) if res % nums[i] == 0]\n",
    "        for f in factor:\n",
    "            idx = bisect_left(nums, f)\n",
    "            if idx == 0 and nums[0] == f or idx < n:\n",
    "                return idx\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = reduce(gcd, numsDivide)\n",
    "        return -1 if (lo := min((x for x in nums if g % x == 0), default=inf)) is inf else sum(x < lo for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        target = reduce(gcd, numsDivide)\n",
    "        nums.sort()\n",
    "        for i,num in enumerate(nums):\n",
    "            if target % num == 0:\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import gcd\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        res = -1\n",
    "        for i in range(len(nums)):\n",
    "            if g%nums[i]==0:\n",
    "                res = i\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = gcd(*numsDivide)\n",
    "        \n",
    "        if all(g % num for num in nums):\n",
    "            return -1\n",
    "\n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            if g % nums[i] == 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        g = 1\n",
    "        first = numsDivide[0]\n",
    "        if len(numsDivide) == 1:\n",
    "            for i, v in enumerate(nums):\n",
    "                if first % v == 0:\n",
    "                    return i\n",
    "        for i in range(1, len(numsDivide)):\n",
    "            g = gcd(first, numsDivide[i])\n",
    "            first = g\n",
    "        for i, v in enumerate(nums):\n",
    "            if g % v == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        g = 1\n",
    "        first = numsDivide[0]\n",
    "        if len(numsDivide) == 1:\n",
    "            for i, v in enumerate(nums):\n",
    "                if first % v == 0:\n",
    "                    return i\n",
    "        for i in range(1, len(numsDivide)):\n",
    "            g = gcd(first, numsDivide[i])\n",
    "            first = g\n",
    "        for i, v in enumerate(nums):\n",
    "            if g % v == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        mn = min((x for x in nums if g % x == 0), default=0)\n",
    "        return sum(x < mn for x in nums) if mn else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # stfinal = set()\n",
    "        # for num in numsDivide:\n",
    "        #     st2=set()\n",
    "        #     i=2\n",
    "        #     while i**2<=num:\n",
    "        #         while num%i ==0:\n",
    "        #             num/=i\n",
    "        #             st2.add(i)\n",
    "        #         i+=1\n",
    "        #     if num>1:\n",
    "        #         st2.add(num)\n",
    "        #     if not len(stfinal):\n",
    "        #         stfinal=st2\n",
    "        #     else:\n",
    "        #         stfinal=stfinal.intersection(st2)\n",
    "        # if stfinal:\n",
    "        #     gcd = reduce(lambda x, y: x*y, stfinal)\n",
    "        # else: \n",
    "        #     gcd = 1\n",
    "        gcd_ = 0\n",
    "        for i in range(len(numsDivide)):\n",
    "            gcd_ = gcd(gcd_,numsDivide[i])\n",
    "        print(gcd_)\n",
    "        for i in range(len(nums)):\n",
    "            if gcd_ % nums[i]==0:\n",
    "                return i\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        return next((i for i, x in enumerate(nums) if g % x == 0), -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        target = reduce(gcd, numsDivide)\n",
    "\n",
    "        mn = min((num for num in nums if target % num == 0), default = 0)\n",
    "        if mn == 0:\n",
    "            return -1\n",
    "        return sum(num < mn for num in nums)\n",
    "        # nums.sort()\n",
    "        # for i,num in enumerate(nums):\n",
    "        #     if target % num == 0:\n",
    "        #         return i\n",
    "        # return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        d = gcd(*numsDivide)\n",
    "        for i, v in enumerate(nums):\n",
    "            if d % v == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        res = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        factor = [nums[i] for i in range(n) if res % nums[i] == 0]\n",
    "        for f in factor:\n",
    "            idx = bisect_left(nums, f)\n",
    "            if idx == 0 and nums[0] == f or idx < n:\n",
    "                return idx\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        n = len(numsDivide)\n",
    "        g = numsDivide[0]\n",
    "        for i in range(1, n):\n",
    "            g = min(gcd(numsDivide[i], g), g)\n",
    "            if g == 1:\n",
    "                break\n",
    "        nums.sort()\n",
    "        # print(g, nums)\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            if x == g or g % x == 0:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        gcdn = numsDivide[0]\n",
    "        for x in numsDivide[1:]:\n",
    "            gcdn = gcd(gcdn, x)\n",
    "        for i in range(len(nums)):\n",
    "            if gcdn % nums[i] == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        g = gcd(*numsDivide)\n",
    "        \n",
    "        nums.sort()\n",
    "        for i in range(n):\n",
    "            if g % nums[i] == 0:\n",
    "                return i\n",
    "                \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a%b)\n",
    "        \n",
    "        nums.sort()\n",
    "        maxyin = numsDivide[0]\n",
    "        for num in numsDivide:\n",
    "            maxyin = gcd(num, maxyin)\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if maxyin % nums[i] == 0:\n",
    "                ans = i\n",
    "        return ans          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        tmp = reduce(gcd, numsDivide)\n",
    "        ret = 0\n",
    "        for x in sorted(nums):\n",
    "            if tmp % x == 0:\n",
    "                break\n",
    "            ret += 1\n",
    "        return ret if ret < len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = int(reduce(gcd, numsDivide))\n",
    "        return -1 if (low := min((x for x in nums if not g % x), default=inf)) is inf else sum(i < low for i in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        g = gcd(*numsDivide)\n",
    "        res = 0\n",
    "        for x in nums:\n",
    "            if g % x == 0:\n",
    "                break\n",
    "            res += 1\n",
    "        return -1 if res == len(nums) else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g_ = numsDivide[0]\n",
    "        for i in range(1, len(numsDivide)):\n",
    "            g_ = gcd(g_, numsDivide[i])\n",
    "\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if g_%nums[i]==0:\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        target = gcd(*numsDivide)\n",
    "        # 分解target的所有因数\n",
    "        factor = set()\n",
    "        for i in range(1, isqrt(target) + 1):\n",
    "            if target % i == 0:\n",
    "                factor.add(i)\n",
    "                factor.add(target // i)\n",
    "        # 寻找nums中最小的在factor中的元素，如果找不到，返回-1\n",
    "        mn = inf\n",
    "        for x in nums:\n",
    "            if x in factor and x < mn:\n",
    "                mn = x\n",
    "        if mn == inf:\n",
    "            return -1\n",
    "        # 寻找nums中小于mn的数的数量\n",
    "        return sum(x < mn for x in nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        # 求一个数组的最大公因数，gcd（*arr)\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        for i,x in enumerate(nums):\n",
    "            if g%x==0:\n",
    "                return i\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "\n",
    "        g = gcd(*numsDivide)\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        return next((i for i, x in enumerate(nums) if g % x == 0), -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        max_divide = numsDivide[0]\n",
    "        for num in numsDivide:\n",
    "            max_divide = self.gcb(max_divide, num)\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if not max_divide % nums[i]:\n",
    "                return i\n",
    "            if nums[i] > max_divide:\n",
    "                return -1\n",
    "        return -1\n",
    "\n",
    "    def gcb(self, max_divide, num):\n",
    "        if not num % max_divide:\n",
    "            return max_divide\n",
    "        return self.gcb(num % max_divide, max_divide)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g=gcd(*numsDivide)\n",
    "        for i,x in enumerate(sorted(nums)):\n",
    "            if x>g:\n",
    "                break\n",
    "            if x==g or g%x==0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        \n",
    "        nums.sort()\n",
    "        maxyin = gcd(*numsDivide)\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if maxyin % nums[i] == 0:\n",
    "                ans = i\n",
    "        return ans          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        def gcd(x, y):\n",
    "            if x>y:\n",
    "                x, y = y, x\n",
    "            while x:\n",
    "                x, y = y%x, x\n",
    "            return y\n",
    "        \n",
    "        a = numsDivide[0]\n",
    "        for i in numsDivide:\n",
    "            a = gcd(a, i)\n",
    "        \n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            if not a%nums[i]:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        mn = min((x for x in nums if g % x == 0), default=0)\n",
    "        return sum(x < mn for x in nums) if mn else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        return next((i for i, x in enumerate(nums) if g % x == 0), -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        for i, x in enumerate(nums):\n",
    "            if g % x == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # stfinal = set()\n",
    "        # for num in numsDivide:\n",
    "        #     st2=set()\n",
    "        #     i=2\n",
    "        #     while i**2<=num:\n",
    "        #         while num%i ==0:\n",
    "        #             num/=i\n",
    "        #             st2.add(i)\n",
    "        #         i+=1\n",
    "        #     if num>1:\n",
    "        #         st2.add(num)\n",
    "        #     if not len(stfinal):\n",
    "        #         stfinal=st2\n",
    "        #     else:\n",
    "        #         stfinal=stfinal.intersection(st2)\n",
    "        # if stfinal:\n",
    "        #     gcd = reduce(lambda x, y: x*y, stfinal)\n",
    "        # else: \n",
    "        #     gcd = 1\n",
    "        gcd_ = 0\n",
    "        for i in range(len(numsDivide)):\n",
    "            gcd_ = gcd(gcd_,numsDivide[i])\n",
    "        # print(gcd_)\n",
    "        for i in range(len(nums)):\n",
    "            if gcd_ % nums[i]==0:\n",
    "                return i\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = reduce(gcd, numsDivide)\n",
    "        m = 2e9\n",
    "        for i, x in enumerate(sorted(nums)):\n",
    "            if g % x == 0: return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        return next((i for i, x in enumerate(nums) if g % x == 0), -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        v = gcd(*numsDivide)\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            if v % x == 0:\n",
    "                return i\n",
    "        \n",
    "        return -1\n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        m=reduce(gcd,numsDivide)\n",
    "        n=len(nums)\n",
    "        for i,now in enumerate(nums):\n",
    "            if m%now==0:\n",
    "                return i\n",
    "            if now>m:\n",
    "                break\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minOperations1(self, nums: List[int], numsDivide: List[int]) -> int:\r\n",
    "        g = gcd(*numsDivide)\r\n",
    "        nums.sort()\r\n",
    "        return next((i for i, x in enumerate(nums) if g % x == 0), -1)\r\n",
    "        \r\n",
    "    # 不排序，两次遍历\r\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\r\n",
    "        g = gcd(*numsDivide)\r\n",
    "        mn = min((x for x in nums if g % x == 0), default=0)\r\n",
    "        return sum(x < mn for x in nums) if mn else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = numsDivide[0]\n",
    "        for i in range(1,len(numsDivide)):\n",
    "            g = gcd(g,numsDivide[i])\n",
    "        nums.sort()\n",
    "        pos = 0\n",
    "        while pos < len(nums) and g % nums[pos]:\n",
    "            pos += 1\n",
    "        return pos if pos != len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        # ans = 0\n",
    "        # cnt = Counter(nums)\n",
    "        # nums = sorted(list(set(nums)))\n",
    "        # numsDivide = set(numsDivide)\n",
    "        # def div(x):\n",
    "        #     for item in numsDivide:\n",
    "        #         if item % x :\n",
    "        #             return False\n",
    "        #     return True\n",
    "\n",
    "        # for item in nums:\n",
    "        #     if div(item):\n",
    "        #         break\n",
    "        #     else:\n",
    "        #         ans+=cnt[item]\n",
    "        \n",
    "        # if ans == sum(cnt.values()):\n",
    "        #     return -1\n",
    "        # else:\n",
    "        #     return ans\n",
    "\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        print([i for i,x in enumerate(nums) if g%x==0])\n",
    "        return  next((i for i,x in enumerate(nums) if g%x==0), -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        def gcd(x, y):\n",
    "            if y == 0:\n",
    "                return x\n",
    "            return gcd(y, x % y)\n",
    "        # 求出numsDivide所有数的最大公因数\n",
    "        num = numsDivide[0]\n",
    "        for i in range(1, len(numsDivide)):\n",
    "            num = gcd(num, numsDivide[i])\n",
    "        \n",
    "        # 将nums排序\n",
    "        nums.sort()\n",
    "        # 寻找nums中第几个数可以整除numsDivide的最大公因数\n",
    "        i = 0\n",
    "        while i < len(nums) and num % nums[i] != 0:\n",
    "            i += 1\n",
    "        return i if i < len(nums) else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        return next((i for i, x in enumerate(nums) if g % x == 0), -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        d = gcd(*numsDivide)\n",
    "        for i, v in enumerate(nums):\n",
    "            if d % v == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        e=numsDivide[0]\n",
    "        for x in numsDivide:\n",
    "            e=gcd(x,e)\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        print(e)\n",
    "        print(nums)\n",
    "        for i in range(n):\n",
    "            x=nums[i]\n",
    "            if gcd(x,e)==x:\n",
    "                return i     \n",
    "        \n",
    "        return -1           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        g = gcd(*numsDivide)\n",
    "        nums.sort()\n",
    "        return next((i for i, x in enumerate(nums) if g % x == 0), -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        g = int(reduce(gcd, numsDivide))\n",
    "        ans = 0\n",
    "        for x in sorted(cnt.keys()):\n",
    "            if g % x == 0:\n",
    "                return ans\n",
    "            ans += cnt[x]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        g = gcd(*numsDivide)\n",
    "        ans = 0\n",
    "        for x in sorted(cnt.keys()):\n",
    "            if g % x == 0:\n",
    "                return ans\n",
    "            ans += cnt[x]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        maxyin = gcd(*numsDivide)\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if maxyin % nums[i] == 0:\n",
    "                if ans == -1:\n",
    "                    ans = nums[i]\n",
    "                else:\n",
    "                    ans = min(ans, nums[i])\n",
    "        if ans == -1:\n",
    "            return ans\n",
    "        return sum([1 if num < ans else 0 for num in nums])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        co = Counter(nums)\n",
    "        nums = list(set(nums))\n",
    "        heapify(nums)\n",
    "        ans = 0\n",
    "        while nums :\n",
    "            p = heappop(nums)\n",
    "            if all(i%p==0 for i in numsDivide):\n",
    "                return ans\n",
    "            ans += co[p]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        print(*nums)\n",
    "        def gcd(a, b):\n",
    "            return a if b == 0 else gcd(b, a%b)\n",
    "        \n",
    "        nums.sort()\n",
    "        maxyin = numsDivide[0]\n",
    "        for num in numsDivide:\n",
    "            maxyin = gcd(num, maxyin)\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if maxyin % nums[i] == 0:\n",
    "                ans = i\n",
    "        return ans          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        maxyin = gcd(*numsDivide)\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if maxyin % nums[i] == 0:\n",
    "                if ans == -1:\n",
    "                    ans = nums[i]\n",
    "                else:\n",
    "                    ans = min(ans, nums[i])\n",
    "        if ans == -1:\n",
    "            return ans\n",
    "        return sum([1 if num < ans else 0 for num in nums])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import heapq\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        heapq.heapify(nums)\n",
    "        gcd_max = numsDivide[0]\n",
    "        for i in range(1, len(numsDivide)):\n",
    "            gcd_max = self.gcd(gcd_max, numsDivide[i])\n",
    "        ans = -1\n",
    "        while nums:\n",
    "            ans += 1\n",
    "            x = heapq.heappop(nums)\n",
    "            if gcd_max % x == 0:\n",
    "                break\n",
    "        else:\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "    def gcd(self, a, b):\n",
    "        while b != 0:\n",
    "            a, b = b, a % b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        import math, heapq, collections\n",
    "        \n",
    "        gcd = math.gcd(*numsDivide)\n",
    "\n",
    "        count = collections.Counter(nums)\n",
    "        heap = []\n",
    "        for k, v in count.items():\n",
    "            heap.append((int(k), v))\n",
    "        heapq.heapify(heap)\n",
    "        ans = 0\n",
    "        while heap:\n",
    "            if gcd % heap[0][0] == 0:\n",
    "                return ans\n",
    "            else:\n",
    "                cur = heapq.heappop(heap) \n",
    "                ans += cur[1]\n",
    "        \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:\n",
    "        a = sorted(Counter(nums).items(), key=lambda x:x[0])\n",
    "        res = 0\n",
    "        for i in a:\n",
    "            ii,jj = i[0], i[1]\n",
    "            flag = False\n",
    "            for j in numsDivide:\n",
    "                if j % ii != 0:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if flag:\n",
    "                res += jj\n",
    "            else:\n",
    "                return res\n",
    "        return -1 if res == len(nums) else res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
